// 版权所有2009年围棋作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// 包堆为实现的任何类型提供堆操作
// 堆接口。堆是一棵树，其属性是每个节点都是
// 其子树中的最小值节点。
// None
// 树中最小的元素是根，索引为0。
// None
// 堆是实现优先级队列的常用方法。建立优先权
// 队列中，以（负）优先级实现堆接口
// 为Less方法排序，因此Push添加项目，而Pop删除项目
// 队列中优先级最高的项目。这些例子包括这样一个例子
// 实施文件example_pq_test.go具有完整的源代码。
// None
package heap

import "sort"

// 接口类型描述了需求
// 对于使用此包中的例程的类型。
// 实现它的任何类型都可以用作
// 具有以下不变量的最小堆（在
// 已调用Init，或者如果数据为空或已排序）：
// None
// !h、 对于0<=i<h.Len（）和2*i+1<=j<=2*i+2和j<h.Len（），小于（j，i）
// None
// 注意，这个接口中的Push和Pop是用于包堆的
// 要调用的实现。要从堆中添加和删除内容，
// 使用heap.Push和heap.Pop。
type Interface interface {
	sort.Interface
	Push(x interface{}) // 将x添加为元素Len（）
	Pop() interface{}   // 拆下并返回元件Len（）-1。
}

// Init建立此包中其他例程所需的堆不变量。
// Init对于堆不变量是幂等的
// 并且可以在堆不变量无效时调用。
// 复杂性为O（n），其中n=h.Len（）。
func Init(h Interface) {
	// 希皮菲
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

// Push将元素x推到堆上。
// 复杂性为O（logn），其中n=h.Len（）。
func Push(h Interface, x interface{}) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop从堆中移除并返回最小元素（根据Less）。
// 复杂性为O（logn），其中n=h.Len（）。
// Pop相当于Remove（h，0）。
func Pop(h Interface) interface{} {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

// Remove从堆中移除并返回索引i处的元素。
// 复杂性为O（logn），其中n=h.Len（）。
func Remove(h Interface, i int) interface{} {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

// Fix在索引i处的元素更改其值后重新建立堆排序。
// 更改索引i处元素的值，然后调用Fix相当于，
// 但成本低于，调用Remove（h，i），然后推送新值。
// 复杂性为O（logn），其中n=h.Len（）。
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // 父母亲
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // int溢出后j1<0
			break
		}
		j := j1 // 左撇子
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // =2*i+2
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}
